Not every individual develops Posttraumatic Stress Disorder (PTSD) after the exposure to a potentially traumatic event. Therefore, the identification of pre-existing risk factors and early diagnostic biomarkers is of high medical relevance. However, no objective biomarker has yet progressed into clinical practice. Sleep disturbances represent commonly reported complaints in PTSD patients. In particular, changes in rapid eye movement sleep (REMS) properties are frequently observed in PTSD patients. Here, we examined in a mouse model of PTSD whether (1) mice developed REMS alterations after trauma and (2) whether REMS architecture before and/or shortly after trauma predicted the development of PTSD-like symptoms. We monitored sleep-wake behavior via combined electroencephalogram/electromyogram recordings immediately before (24 h pre), immediately after (0–48 h post) and 2 months after exposure to an electric foot shock in male C57BL/6N mice (n = 15). PTSD-like symptoms, including hyperarousal, contextual, and generalized fear, were assessed 1 month post-trauma. Shocked mice showed early onset and sustained elevation of REMS compared to non-shocked controls. In addition, REMS architecture before trauma was correlated with the intensity of acoustic startle responses, but not contextual fear, 1 month after trauma. Our data suggest REMS as prognostic (pre-trauma) and symptomatic (post-trauma) marker of PTSD-like symptoms in mice. Translated to the situation in humans, REMS may constitute a viable, objective, and non-invasive biomarker in PTSD and other trauma-related psychiatric disorders, which could guide pharmacological interventions in humans at high risk.